# @Author: Eric Ito
# @Date: 2/2/2009
# @Name: Project Euler Problem 41


"""
What is the largest n-digit pandigital prime number that exists
"""

from util import isPrime
from util import isNPandigital

def makeString(tpl):
    outStr = ""
    for item in tpl:
        outStr += str(item)
    return outStr

def genPrimes(n):
    '''Generates a list of prime numbers up to n'''
    primes = []
    CROSS_LIST = []
    for i in range(3,n,2):
        if isNPandigital(i,len(str(n))):
           CROSS_LIST.append(i)
    for i in range(3,int(n**0.5),2):
        for j in CROSS_LIST:
            if not j==i and j % i == 0:
                CROSS_LIST.remove(j)
    return [2] + CROSS_LIST

def main():
    p = genPrimes(578649123)
    print max(p)
    #for j in range(len(p)-1,0,-1):
    #    if isPrime(p[j]) and isNPandigital(p[j],len(p[j])):
    #        print p[j]
    #        return
    return
    USED = []
    largest = 0
    for a in range(1,10):
        USED.append(a)
        for b in range(1,10):
            if b in USED:
                continue
            USED.append(b)
            for c in range(1,10):
                if c in USED:
                    continue
                USED.append(c)
                for d in range(1,10):
                    if d in USED:
                        continue
                    USED.append(d)
                    for e in range(1,10):
                        if e in USED:
                            continue
                        USED.append(e)
                        for f in range(1,10):
                            if f in USED:
                                continue
                            USED.append(f)
                            for g in range(1,10):
                                if g in USED:
                                    continue
                                USED.append(g)
                                for h in range(1,10):
                                    if h in USED:
                                        continue
                                    USED.append(h)
                                    for i in range(1,10):
                                        if i in USED or i % 2 == 0:
                                            continue
                                        num = makeString([a,b,c,d,e,f,g,h,i])
                                        print num
                                        if isNPandigital(num,9) and isPrime(int(num)):
                                            print num,largest
                                            if int(num) > largest:
                                                print 'assigning'
                                                largest = int(num)
                                            print largest
                                    USED.remove(h)
                                USED.remove(g)
                            USED.remove(f)
                        USED.remove(e)
                    USED.remove(d)
                USED.remove(c)
            USED.remove(b)
        USED.remove(a)
    print largest


if __name__ == "__main__":
    main()